package leetcode.code0239;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution extends Solution239 {

	class Pos {
		public int val; // pos.val 原数组中的数值
		public int index;// pos.index 原数组中的脚标

		public Pos(int val, int index) {
			this.val = val;
			this.index = index;
		}
	}

	private class Heap {
		Pos[] array; // 堆上数据 pos.val 原数组中的数值, pos.index 原数组中的脚标
		int limit;// 堆上限, 最多放多少个数, 本问题中==k
		int heapSize;// 堆上数量, 当前可用脚标, 在构建从[0,k-1]的过程中起到指引当前可用脚标的作用
		Map<Integer, Integer> srcHeap;// Map<原数组index,在堆上位置>
		int minIndex;// 当前堆上最小的原数组索引, 开始是0, replace过程中, 每次+1 == 进入堆一个新数, 出去一个最小的index

		public Heap(int limit) {
			this.limit = limit;
			this.array = new Pos[limit];
			this.heapSize = 0;
			this.srcHeap = new HashMap<>();
			this.minIndex = 0;
		}

		public int peek() {
			return this.array[0].val;// 堆顶
		}

		public void add(int val, int index) {// 从空堆构建到k个数堆
//			if (this.heapSize < this.limit) { // 堆有空, 拆成add和replace两个方法, 减少不必要的if else
				this.array[this.heapSize] = new Pos(val, index);
				this.srcHeap.put(index, this.heapSize);// 原数组index在堆上位置为heapSize
				this.heapInsert(this.heapSize);
				this.heapSize++;
//			} else {
//				int indexOnHeap = this.srcHeap.get(this.minIndex);
//				this.minIndex++;
//				this.array[indexOnHeap] = new Pos(val, index);
//				this.heapInsert(indexOnHeap);
//				this.heapify(indexOnHeap);
//			}
		}

		public void replace(int val, int index) {
			int indexOnHeap = this.srcHeap.get(this.minIndex);// 原数组最小索引在堆上的位置
			this.minIndex++;// 对小位置提升
			this.srcHeap.put(index, indexOnHeap);// 被替换的位置放新val index
			this.array[indexOnHeap] = new Pos(val, index);// 被替换的位置放新val index
			this.heapInsert(indexOnHeap);// 看看是否需要heapInsert
			this.heapify(indexOnHeap);// 看看是否需要heapify
		}

		private void heapify(int index) {// 从上向下移动
			int left = (index << 1) | 1;
			while (left < limit) {
				int largest = left + 1 < limit && this.array[left + 1].val > this.array[left].val ? left + 1 : left;
				largest = this.array[largest].val > this.array[index].val ? largest : index;
				if (largest == index)
					break;
				swap(index, largest);
				index = largest;
				left = (index << 1) | 1;
			}
		}

		private void heapInsert(int index) {// 从下向上移动
			int p = (index - 1) / 2;
			while (array[index].val > array[p].val) {
				swap(index, p);
				index = p;
				p = (index - 1) / 2;
			}
		}

		private void swap(int index, int p) {
			this.srcHeap.put(this.array[index].index, p);// 交换索引在堆上的位置
			this.srcHeap.put(this.array[p].index, index);// 交换索引在堆上的位置
			Pos temp = this.array[index];
			this.array[index] = this.array[p];
			this.array[p] = temp;
		}

	}

	@Override
	public int[] maxSlidingWindow(int[] nums, int k) {
		if (k == 1)
			return nums;
		int i = 0;
		List<Integer> ansList = new ArrayList<>();
		Heap heap = new Heap(k);
		for (; i < k; i++) {// 构建k个长度的窗口
			heap.add(nums[i], i);// add
		}
		ansList.add(heap.peek());// 窗口内第一个最大值
		for (; i < nums.length; i++) {
			heap.replace(nums[i], i);// replace 替换堆中最小index的值
			ansList.add(heap.peek());// 替换后的最大值
		}
		int[] ans = new int[ansList.size()];// list转array
		int p = 0;
		for (int num : ansList) {
			ans[p++] = num;
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
